(1) Field of the Invention
The present invention relates to the field of searching an entries within an allocation designation to discover free locations. Specifically the present invention relates to the field of searching an entry vector for the first of a predetermined number of free entries within a reservation station.
(2) Prior Art
Modern microprocessors are gaining the ability to execute portions of several instructions in parallel during a single clock cycle. These microprocessors are called superscalar microprocessors and have pipelined and/or superscalar architecture. In effect, different stages of execution can be performed by a microprocessor during a single clock cycle for several different microprocessor instructions. For this reason and others, microprocessors having this ability must be able to keep track of and store information regarding several instructions at the same time and communicate this information to and from several different portions of the microprocessor in a parallel fashion. Also, because of the high operating frequencies of modern pipelined microprocessors, this instruction information must be transmitted very quickly, usually during a single clock cycle of an oscillator operating at 150-200 Megahertz. Therefore, it becomes advantageous to be able to communicate instructions and instruction data very quickly in a parallel fashion to the various units of a microprocessor.
One component within a microprocessor that must receive information regarding instructions that are being executed by a microprocessor is the instruction scheduler. The instruction scheduler holds information regarding the current instructions that are being executed as well as any data or information that is used by or in conjunction with the current instructions. The instruction scheduler has a finite memory storage capacity. Therefore, new and recent instruction information that is to be placed into the scheduler by the microprocessor must first obtain enough memory location vacancies within the instruction scheduler. That is to say, there must first be room within the scheduler before instruction information can be placed into the instruction scheduler.
A specialized deallocation vector is used by the instruction scheduler in order to indicate to the microprocessor which entries in the instruction scheduler are free and which are taken. In prior art implementations, the microprocessor would scan, one by one, each entry in the deallocation vector to locate one particular free entry of the instruction scheduler in order to store recent instruction data. However, with the introduction of microprocessors having superscalar architecture, the microprocessor must be able to search, at the same instant, the deallocation vector for up to several free entries to store information regarding several instructions during the same clock cycle. Further, as the time period between clock cycles shortens as microprocessors become faster and faster, it is important that the deallocation vector be searched very quickly as to not delay the processing of the microprocessor.
Prior art implementations used to search a deallocation vector in order to find vacancies within the instruction scheduler do not operate fast enough to complete processing within only one clock cycle (which may be on the order of 1/150th of a microsecond) or within one half clock cycle (which may be 1/300th of a microsecond) of modern superscalar microprocessors. It is not practical, given the environment of a pipelined microprocessor, to sequentially search each and every entry in a deallocation vector in order to discover, at the same instant, several vacant entries within the instruction scheduler. Since it is desired for pipelined microprocessors to execute portions of several instructions in parallel, it is unacceptable for there to be any delays associated with the search procedure of the deallocation vector of the instruction scheduler. This procedure must operate within a single clock cycle. Delays associated with such a task would reduce overall microprocessor efficiency and speed. Further, such processing delays may tend to eliminate the expansive advantages offered by microprocessors adopting pipeline architecture and associated microprocessor technology.
Therefore, what is desired is a processing scheme and apparatus that would allow very rapid searching of a deallocation vector in order to find, in one clock cycle, several vacant entries within an instruction scheduler. The present invention offers such advantageous capability.
Accordingly, it is an object of the present invention to provide a method and apparatus for searching a deallocation vector, within a single clock cycle, in order to locate several vacancies within a reservation station of an instruction scheduler. It is another object of the present invention to provide the above capability so that a pipelined architecture microprocessor can store instruction information for several instructions, which are or will be currently executed, into the instruction scheduler within the period one clock cycle. It is further an object of the present invention to provide such a system that operates very rapidly and will complete within one half of a clock cycle of the microprocessor, which may be less than 1/300th of a microsecond. Other objects of the present invention not specifically mentioned herein will become clear within the remainder of the discussions below.